package org.example.myleet.p503;

import java.util.Stack;

public class Solution {
    /**
     * 7 ms
     * 利用栈的维护一个单调性的位置代表数字由大到小（栈底到栈顶）的排列，使得观察到的数字如果比栈顶大，则一定是栈顶的下一个更大值
     */
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            //特殊情况
            return new int[]{};
        }
        int max = nums[0];
        //存储结果
        int[] reply = new int[n];
        //存储当前未找到下一个更大值的位置，其记录的顺序中，栈顶的位置代表的数字更小，栈底的位置代表的数字是当前观察到最大
        Stack<Integer> positionStack = new Stack<>();
        //初始化0是未找到下一个更大值的位置
        positionStack.push(0);
        for (int i=1; i<n; i++) {
            while (!positionStack.isEmpty() && nums[i] > nums[positionStack.peek()]) {
                //如果栈顶的位置代表的数字比当前观察值小，说明找到栈顶位置的下一个更大值，记录结果并弹出，直到遇到比观察值更大的位置，停下来
                reply[positionStack.pop()] = nums[i];
            }
            //观察到的位置未找到下一个更大值，入栈
            positionStack.push(i);
            //记录出现过的最大值
            max = Math.max(max, nums[i]);
        }
        if (max != nums[positionStack.peek()]) {
            //如果最大值是栈顶的位置的值，那么就不用再循环一遍数组，因为除最大值外已经都找到下一个更大值
            //但是如果栈顶的位置的值不是最大值，需要循环一遍数组找到这些位置的下一个更大值
            for (int i = 0; i < n; i++) {
                while (!positionStack.isEmpty() && nums[i] > nums[positionStack.peek()]) {
                    //找到就记录结果并弹出
                    reply[positionStack.pop()] = nums[i];
                }
            }
        }
        //最后剩下的肯定是最大值的位置，全部记为-1
        while (!positionStack.isEmpty()) {
            reply[positionStack.pop()] = -1;
        }
        return reply;
    }
}
